---
id: 图的最短路径
title: 最短路径
---

## Dijkstra算法

:::info 
这是一个迭代算法，得出从一个顶点到其余所有顶点的最短路径，很接近于广度优先搜索算法BFS的结果。  
具体实现上，在顶点Vertex类中的成员 dist用于记录从开始顶点到本顶点的最短带权路径长度(权重之和)，算法对图中的每个顶点迭代一次。
:::

### 代码实现
- 顶点的访问次序由一个优先队列来控制，队列中作为优先级的是顶点的dist属性。
- 最初， 只有开始顶点dist设为0， 而其他所有顶点dist设为sys.maxsize（最大整数） ， 全部加入优先队列。
- 随着队列中每个最低dist顶点率先出队
- 并计算它与邻接顶点的权重， 会引起其它顶点dist的减小和修改， 引起堆重排
- 并据更新后的dist优先级再依次出队

```python
from pythonds.graphs import PriorityQueue,Graph,Vertex

def dijkstra(aGraph,start):
    pq = PriorityQueue();
    start.setDistance(0);
    pq.buildHeap([(v.getDistance(),v) for v in aGraph]);
    while not pq.isEmpty():
        currentVert = pq.delMin();
        for nextVert in currentVert.getConnections():
            newDist= currentVert.getDistance() + currentVert.getWeight(nextVert);
            if newDist < nextVert.getDistance():
                nextVert.setDistance(newDist);
                nextVert.setPred(currentVert);
                pq.decreaseKey(nextVert,newDist);

```

### Dijkstra算法分析
- Dijkstra算法只能处理大于0的权重，如果图中出现负数权重，则算法会陷入无限循环
- 首先， 将所有顶点加入优先队列并建堆，时间复杂度为O(|V|)
- 其次， 每个顶点仅出队1次， 每次delMin花费O(log|V|)， 一共就是O(|V|log|V|)
- 另外， 每个边关联到的顶点会做一次decreaseKey操作（O(log|V|))， 一共是O(|E|log|V|)
- 上面三个加在一起，数量级就是O((|V|+|E|)log|V|)